import collections
from typing import List


class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        stat = tuple(board[0] + board[1])
        visited = {stat: 0}
        queue = collections.deque([stat])

        while queue:
            stat1 = queue.popleft()
            if stat1 == (1, 2, 3, 4, 5, 0):
                return visited[stat1]
            for stat2, need in [[(stat1[1], stat1[0], stat1[2], stat1[3], stat1[4], stat1[5]), [0, 1]],
                                [(stat1[0], stat1[2], stat1[1], stat1[3], stat1[4], stat1[5]), [1, 2]],
                                [(stat1[0], stat1[1], stat1[2], stat1[4], stat1[3], stat1[5]), [3, 4]],
                                [(stat1[0], stat1[1], stat1[2], stat1[3], stat1[5], stat1[4]), [4, 5]],
                                [(stat1[3], stat1[1], stat1[2], stat1[0], stat1[4], stat1[5]), [0, 3]],
                                [(stat1[0], stat1[4], stat1[2], stat1[3], stat1[1], stat1[5]), [1, 4]],
                                [(stat1[0], stat1[1], stat1[5], stat1[3], stat1[4], stat1[2]), [2, 5]]]:
                if stat2[need[0]] != 0 and stat2[need[1]] != 0:  # 判断交换位置是否包含0
                    continue
                if stat2 not in visited:
                    visited[stat2] = visited[stat1] + 1
                    queue.append(stat2)

        # for k, v in visited.items():
        #     print(k, ":", v)

        return visited[(1, 2, 3, 4, 5, 0)] if (1, 2, 3, 4, 5, 0) in visited else -1


if __name__ == "__main__":
    # 1
    print(Solution().slidingPuzzle(board=[[1, 2, 3],
                                          [4, 0, 5]]))

    # -1
    print(Solution().slidingPuzzle(board=[[1, 2, 3],
                                          [5, 4, 0]]))

    # 5
    print(Solution().slidingPuzzle(board=[[4, 1, 2],
                                          [5, 0, 3]]))

    # 14
    print(Solution().slidingPuzzle(board=[[3, 2, 4],
                                          [1, 5, 0]]))
